#include <bits/stdc++.h>

#define N 100005

using namespace std;

vector <int> g[N];
int vis[N] = {0};
queue <int> q;

void dfs(int n){
    printf("%d ", n);
    for(int i = 0; i < g[n].size(); i++){
        if(!vis[g[n][i]]){
            vis[g[n][i]] = 1;
            dfs(g[n][i]);
        }
    }
}

void bfs(){
    queue <int> q;
    q.push(1);
    while(!q.empty()){
        int x = q.front();  q.pop();
        printf("%d ", x);
        for(int i = 0; i < g[x].size(); i++){
            if(!vis[g[x][i]]){
                vis[g[x][i]] = 1;
                q.push(g[x][i]);
            }
        }
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    int x, y;
    for(int i = 1; i <= m; i++){
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
    }
    for(int i = 1; i <= m; i++){
        sort(g[i].begin(), g[i].end());
    }
    vis[0] = 1;
    vis[1] = 1;
    dfs(1);
    cout << "\n";
    memset(vis, 0, sizeof(vis));
    vis[0] = 1;
    vis[1] = 1;
    bfs();
    /*for(int i = 1; i <= n; i++){
        cout << i << ":";
        for(int j = 0; j < g[i].size(); j++){
            cout <<g[i][j] << " ";
        }
        cout << "\n";
    }*/
    return 0;
}